import java.io.*;
import java.util.Scanner;

public class FloydShortestPath{
    static int numNodes;
   public static DigraphNode nodes[];
    
    public static void main(String[] args) throws IOException {
       readDigraph();
       Floyd(); 
       }
    
    

      public static void Floyd() {

       int Next[][] = new int [numNodes][numNodes];
       double F[][] = new double [numNodes][numNodes];
      
       for(int i = 0; i < numNodes; i++){
    	   for(int j = 0; j < numNodes; j++)
    		   if( i != j)
    			   F[i][j] = 99.9;
    		   else F[i][j] = 0.0;
       }
       
       for(int k = 0; k < numNodes; k++){
    	   for (int l = 0; l < nodes[k].degree; l++){
    		   F[k][nodes[k].info[l].nextNodeOnPath] = nodes[k].info[l].pathLength;
    	   }
       }
       
       for(int m = 0; m < numNodes; m++){
    	   System.out.println("F:" + m);
    	   for(int n = 0; n < numNodes; n++){
    		   System.out.println();
    		   for(int p = 0; p < numNodes; p++){
    			   System.out.print( F[n][p] + "  ");
    		   if( n != m && p != m)
                   if (F[n][m] + F[m][p] < F[n][p]){
                       F[n][p] = F[n][m] + F[m][p];
                       Next[n][p] = m;                      
                   }else
                       F[n][p] = F[n][p];
       
               }}}}  
 
                     
    public static void readDigraph() throws IOException {

        File input = new File("digraph.data");
        Scanner digraph = new Scanner(input).useDelimiter("\\s+(\\()?|\\(|\\)(\\:)?(\\s+)?");

        if (digraph.hasNext()) {

            int nodeNum;
            numNodes = digraph.nextInt(); digraph.nextLine();

            nodes = new DigraphNode[numNodes];
            
            while (digraph.hasNext()) {
                nodeNum = digraph.nextInt(); 
                nodes[nodeNum] = new DigraphNode(nodeNum, digraph.nextInt());

                for (int i = 0; i < nodes[nodeNum].degree; i++) {
                   nodes[nodeNum].info[i] = new LengthAndNext(digraph.nextInt(), digraph.nextDouble());
                } 
            }
        }
        else return; 
    }
}